package com.offer;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-12-04 16:57
 * @version: 1.0
 * @description: 包含min函数的栈
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 **/
public class MinStack {
    Deque<Integer> stack;
    Deque<Integer> sortStack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
        sortStack = new ArrayDeque<>();
        sortStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        sortStack.push(Math.min(x,sortStack.peek()));
    }

    public void pop() {
        stack.pop();
        sortStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
       return sortStack.pop();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
//        minStack.push(-0);
//        minStack.push(-3);
//        System.out.println(minStack.min());
//        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.min());
    }
}
